#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using AbstractClass.Extensions;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a data structure for storing a sorted list of items, using a
    /// hierarchy of linked lists that connect increasingly sparse subsequences of
    /// the items. These auxiliary lists allow item lookup with efficiency comparable
    /// to balanced binary search trees.
    /// </summary>
    /// <typeparam name="T">The type of the data in the collection.</typeparam>
    public class SkipList<T> : IAlgorithmAwareCollection<T, SkipList<T>>
    {
        /// <summary>
        /// The probability associated with the <see cref="SkipList&lt;T&gt;"/>.
        /// </summary>
        [CLSCompliant(false)]
        protected readonly double _Probability = 0.5;

        private readonly IComparer<T> _comparer = Comparer<T>.Default;

        private readonly Random _randomNumber;
        private SkipListNode<T> _head;

        /// <summary>
        /// Initializes a new instance of the <see cref="SkipList&lt;T&gt;"/> class.
        /// </summary>
        public SkipList() : this(-1, null)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="SkipList&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="randomSeed">The random seed needed to randomize the addition
        /// of forward links.</param>
        public SkipList(int randomSeed) : this(randomSeed, null)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="SkipList&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="comparer">The <see cref="IComparer&lt;T&gt;"/> implementation to use
        /// when comparing the elements.</param>
        public SkipList(IComparer<T> comparer) : this(-1, comparer)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="SkipList&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="randomSeed">The random seed needed to randomize the addition
        /// of forward links.</param>
        /// <param name="comparer">The <see cref="IComparer&lt;T&gt;"/> implementation to use
        /// when comparing the elements.</param>
        public SkipList(int randomSeed, IComparer<T> comparer)
        {
            _head = new SkipListNode<T>(1);
            Count = 0;
            Count++;
            _randomNumber = randomSeed < 0 ? new Random() : new Random(randomSeed);

            if (comparer != null) _comparer = comparer;
        }

        #region Implementation of IEnumerable

        /// <summary>
        ///   Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        ///   A <see cref = "IEnumerator&lt;T&gt;" /> that can be used to iterate through the collection.
        /// </returns>
        public IEnumerator<T> GetEnumerator()
        {
            SkipListNode<T> current = _head[0];
            while (current != null)
            {
                yield return current.Value;
                current = current[0];
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        /// <summary>
        /// Gets the probability associated with this instance.
        /// </summary>
        /// <value>The probability.</value>
        public double Probability
        {
            get { return _Probability; }
        }

        /// <summary>
        /// Gets the <see cref="IComparer&lt;T&gt;"/> implementation to use
        /// when comparing the elements.
        /// </summary>
        /// <value>The comparer to sort the elements in the list.</value>
        public IComparer<T> Comparer
        {
            get { return _comparer; }
        }

        /// <summary>
        /// Returns a random height required to insert new element.
        /// </summary>
        /// <param name="maxLevel">Maximum allowable level.</param>
        /// <returns>The new height for the new node.</returns>
        protected virtual int ChooseRandomHeight(int maxLevel)
        {
            int level = 1;
            while (_randomNumber.NextDouble() < _Probability && level < maxLevel)
                level++;

            return level;
        }

        /// <summary>
        /// Finds a specified item in the collection.
        /// </summary>
        /// <param name="item">The item to find.</param>
        /// <returns>
        /// The <see cref="SkipListNode&lt;T&gt;"/> associated with <paramref name="item"/> if found;
        /// otherwise, <c>null</c>.
        /// </returns>
        public SkipListNode<T> Find(T item)
        {
            SkipListNode<T> current = _head;
            for (int i = _head.Height - 1; i >= 0; i--)
            {
                while (current[i] != null)
                {
                    int results = _comparer.Compare(current[i].Value, item);
                    if (results == 0)
                        return current[i];
                    if (results < 0)
                        current = current[i];
                    else
                        break;
                }
            }
            return null;
        }

        #region Implementation of ICollection<T>

        /// <summary>
        /// Gets the height of the head node.
        /// </summary>
        /// <value>The height of head node.</value>
        public int Height
        {
            get { return _head.Height; }
        }

        /// <summary>
        /// Adds <paramref name="item"/> in the collection.
        /// </summary>
        /// <param name="item">The specified item to add.</param>
        public void Add(T item)
        {
            SkipListNode<T>[] updates = BuildUpdateTable(item);
            SkipListNode<T> current = updates[0];

            if (current[0] != null && _comparer.Compare(current[0].Value, item) == 0)
                return;

            var n = new SkipListNode<T>(item, ChooseRandomHeight(_head.Height + 1));
            Count++;

            if (n.Height > _head.Height)
            {
                _head.IncrementHeight();
                _head[_head.Height - 1] = n;
            }

            for (int i = 0; i < n.Height; i++)
            {
                if (i >= updates.Length) continue;
                n[i] = updates[i][i];
                updates[i][i] = n;
            }
        }

        /// <summary>
        /// Clears all items from the collection.
        /// </summary>
        public virtual void Clear()
        {
            _head = null;
            _head = new SkipListNode<T>(1);
            Count = 0;
        }

        /// <summary>
        /// Determines whether the <paramref name="item"/> is in the collection.
        /// </summary>
        /// <param name="item">The specified item to find in the collection.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="item"/> is found; otherwise, <c>false.</c>
        /// </returns>
        public bool Contains(T item)
        {
            SkipListNode<T> current = _head;

            for (int i = _head.Height - 1; i >= 0; i--)
            {
                while (current[i] != null)
                {
                    int results = _comparer.Compare(current[i].Value, item);
                    if (results == 0)
                        return true;
                    if (results < 0)
                        current = current[i];
                    else
                        break;
                }
            }
            return false;
        }

        /// <summary>
        /// Copies the elements of the <see cref = "SkipList&lt;T&gt;" /> to an array of type
        /// T, starting at the specified array index.
        /// </summary>
        /// <param name="array">The one-dimensional array of type T that is the destination of
        /// the elements copied from the <see cref = "SkipList&lt;T&gt;" />. The array must have zero-based indexing.
        ///	 </param>
        /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="arrayIndex"/> is not positive.</exception>
        /// <exception cref="ArithmeticException"><paramref name="arrayIndex"/> is greater than the length of <paramref name="array"/>. </exception>
        /// <exception cref="ArgumentException">Difference of <paramref name="array"/> size and <paramref name="arrayIndex"/>
        /// is not greater than the total size of the <see cref = "SkipList&lt;T&gt;" />.
        /// </exception>
        public void CopyTo(T[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex");

            if (arrayIndex >= array.Length)
                throw new ArithmeticException(LanguageResource.IndexIsGreaterThanTheLengthOfArray);

            if (array.Length - arrayIndex <= Count)
                throw new ArgumentException(LanguageResource.SkipListInsufficientSpace);

            SkipListNode<T> current = _head[0];
            int i = 0;
            while (current != null)
            {
                array[i + arrayIndex] = current.Value;
                i++;
            }
        }

        /// <summary>
        /// Removes <paramref name="item"/> from the <see cref = "SkipList&lt;T&gt;" />.
        /// </summary>
        /// <param name="item">The specified item to remove from <see cref = "SkipList&lt;T&gt;" />.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="item"/> is removed successfully; otherwise, <c>false</c>.
        /// </returns>
        public bool Remove(T item)
        {
            SkipListNode<T>[] updates = BuildUpdateTable(item);
            SkipListNode<T> current = updates[0][0];

            if (current != null && _comparer.Compare(current.Value, item) == 0)
            {
                Count--;
                for (int i = 0; i < _head.Height; i++)
                {
                    if (updates[i][i] != current)
                        break;
                    updates[i][i] = current[i];
                }

                if (_head[_head.Height - 1] == null)
                    _head.DecrementHeight();

                return true;
            }
            return false;
        }

        /// <summary>
        /// Gets the total number of elements in the <see cref = "SkipList&lt;T&gt;" />.
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// Determines whether the <see cref = "SkipList&lt;T&gt;" /> is read-only.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Returns the updated collection after a possible alteration of the <see cref = "SkipList&lt;T&gt;" />.
        /// </summary>
        /// <param name="value">The specified item to be removed/added from/to the <see cref = "SkipList&lt;T&gt;" />.</param>
        /// <returns>
        /// The updated collection of <see cref = "SkipListNode&lt;T&gt;" />.
        /// </returns>
        protected SkipListNode<T>[] BuildUpdateTable(T value)
        {
            var updates = new SkipListNode<T>[_head.Height];
            SkipListNode<T> current = _head;

            for (int i = _head.Height - 1; i >= 0; i--)
            {
                while (current[i] != null && _comparer.Compare(current[i].Value, value) < 0)
                {
                    current = current[i];
                }
                updates[i] = current;
            }
            return updates;
        }

        #endregion

        #region Implementation of IAlgorithmAware<out SkipList<T>>

        /// <summary>
        /// Executes the <paramref name="algorithm"/> on the <see cref = "SkipList&lt;T&gt;" />.
        /// </summary>
        /// <typeparam name="TResult">The type of the result.</typeparam>
        /// <param name="algorithm">The algorithm to run on the <see cref = "SkipList&lt;T&gt;" />.</param>
        /// <returns>The result of execution of the <paramref name="algorithm"/> on the <see cref = "SkipList&lt;T&gt;" />.</returns>
        public TResult ExecuteAlgorithm<TResult>(IAlgorithm<SkipList<T>, TResult> algorithm)
        {
            algorithm.ThrowIfNull("algorithm");
            return algorithm.Run(this);
        }

        #endregion
    }
}